//给你两个正整数 n 和 limit 。 
//
// 请你将 n 颗糖果分给 3 位小朋友，确保没有任何小朋友得到超过 limit 颗糖果，请你返回满足此条件下的 总方案数 。 
//
// 
//
// 示例 1： 
//
// 
//输入：n = 5, limit = 2
//输出：3
//解释：总共有 3 种方法分配 5 颗糖果，且每位小朋友的糖果数不超过 2 ：(1, 2, 2) ，(2, 1, 2) 和 (2, 2, 1) 。
// 
//
// 示例 2： 
//
// 
//输入：n = 3, limit = 3
//输出：10
//解释：总共有 10 种方法分配 3 颗糖果，且每位小朋友的糖果数不超过 3 ：(0, 0, 3) ，(0, 1, 2) ，(0, 2, 1) ，(0, 3,
// 0) ，(1, 0, 2) ，(1, 1, 1) ，(1, 2, 0) ，(2, 0, 1) ，(2, 1, 0) 和 (3, 0, 0) 。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 50 
// 1 <= limit <= 50 
// 
//
// Related Topics 数学 组合数学 枚举 👍 56 👎 0


package LeetCode.editor.cn;

/**
 * @author ldltd
 * @date 2024-06-04 16:07:11
 * @description 2928.给小朋友们分糖果 I
 */
public class DistributeCandiesAmongChildrenI{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 DistributeCandiesAmongChildrenI fun=new DistributeCandiesAmongChildrenI();
	 	 Solution solution = fun.new Solution();
		 System.out.println(solution.distributeCandies(5, 2));
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int distributeCandies(int n, int limit) {
		return dfs(n,limit,1);
    }
	public int dfs(int n,int limit,int i){
		if(i==3){
			return (n<=limit&&n>=0)?1:0;
		}
		int res=0;
		for (int j = i; j < 3; j++) {
			for (int k = 0; k <=limit; k++) {
				int dfs = dfs(n - k, limit, j + 1);
				res+= dfs;
			}
		}
		return res;
	}
	//枚举优化
	public int distributeCandies1(int n, int limit) {
		int ans = 0;
		for (int i = 0; i <= Math.min(limit, n); i++) {
			//枚举第一个分的糖果，
			//如果n-i>limit*2，则不存在合法的
			if (n - i > 2 * limit) {
				continue;
			}
			//如果存在，第二个小朋友至少分max(0,n-i-limit)个糖
			//至多分min(limit,n-x)颗
			//比如分3~5颗，就有5-3+1种方案
			ans += Math.min(n - i, limit) - Math.max(0, n - i - limit) + 1;
		}
		return ans;
	}

	/*容斥原理
	* 所有方案，减去不合法的
	* 至少一个超过limit，变成剩下的分n-limit-1个
	* 方案数3xC(n-limit-1+2,2)
	* 但重复统计了至少两个超过limit
	* 先分给两个limit+2，问题变成剩下n-2*Limit-2分的方案
	* 即3xC（n-2*limit-2+2,2)
	* 至少两个超过limit包含了三个超过limit的情况要减去
	* 三个超过limit的方案为
	* C(n-3*limit-3+2,2)
	*
	* 不合法的方案数为「至少一个」减去「至少两个」加上「三个」，这就是容斥原理
	*
	* 之所以+2，是把糖果中间加隔板，相当于把n个球和2个隔板放入n+2个位置，挑两个位置放隔板
	* C（n,2)等于 n*(n-1)/2
	* */
	public int distributeCandies2(int n, int limit) {
		return cal(n + 2) - 3 * cal(n - limit + 1) + 3 * cal(n - (limit + 1) * 2 + 2) - cal(n - 3 * (limit + 1) + 2);
	}

	public int cal(int x) {
		if (x < 0) {
			return 0;
		}
		return x * (x - 1) / 2;
	}

}
//leetcode submit region end(Prohibit modification and deletion)

}
